#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
/*
喝汽水，1瓶汽水1元，2个空瓶可以换一瓶汽水，
给20元，可以喝多少汽水（编程实现）。
*/

int fun1(int n)
{
    int empty = n;  //空瓶子
    int drinks = n; //喝掉的汽水总数

    while(empty >= 2)
    {
        int new_drinks = empty / 2; //新兑换的
        drinks += new_drinks;
        empty = empty % 2 + new_drinks;
    }
    return drinks;
}

/*
调整数组使奇数全部都位于偶数前面。
题目：
输入一个整数数组，实现一个函数，
来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分，
所有偶数位于数组的后半部分。
*/

//定义三个指针 left从左边 代表奇数的位置，标记最右边奇数的位置，
//right从右边 代表偶数的位置，标记最右边的偶数的位置
//ptr 遍历数组 当ptr和right相遇 就可以结束了， 因为right右边全是偶数
//left左边也全是奇数
int fun2(int* arr, int len)
{
    int* left = arr;
    int* right = arr+len-1;
    int* ptr = arr;

    while(ptr < right)
    {
        //奇数
        if((*ptr)%2 == 1)
        {
            if(ptr == left) //如果left和ptr相等不用交换
            {
                left++;
                ptr++;
            }
            else 
            {
                int tmp = *left;
                *left = *ptr;
                *ptr = tmp;
                left++;
                //交换ptr和left 此时left前面全是奇数，left++
                if((*ptr)%2 == 1) //如果该位置  还是奇数 也往前继续走 ptr++
                    ptr++;
                
            }     
        }

        //偶数
        else if((*ptr)%2 == 0)
        {
            if(ptr == right) //如果left和ptr相等不用交换
            {
                right--;
                ptr++;
            }
            else
            {
                int tmp = *right;
                *right = *ptr;
                *ptr = tmp;
                right--; 
                if((*ptr)%2 == 0)
                ptr++;
                      
            }     
        }
    }
}

//三指针的方式 有点麻烦，尝试一下双指针能不能做到呢

//初步想法，left标记左边，right标记右边
//left指向的是左边奇数就++向前走，同时right指向的是右边的偶数的话
//就--往前走，当left指向的是偶数，停下来，且right指向了奇数也停下来
//且还没有和right相遇的时候，left和right交换，然后两个继续遍历直到相遇


/*
思路：
1. 给定两个下标left和right，left放在数组的起始位置，right放在数组中最后一个元素的位置
2. 循环进行一下操作
 a. 如果left和right表示的区间[left, right]有效，进行b，否则结束循环
 b. left从前往后找，找到一个偶数后停止
 c. right从后往前找，找到一个奇数后停止
 d. 如果left和right都找到了对应的数据，则交换，继续a，
*/
//
void fun3(int* arr, int len)
{
    int* left = arr;
    int* right = (arr+len-1);

    while(left < right)
    {
        while((*left)%2 == 1) //奇数
            left++;
        while((*right)%2 == 0) //偶数
            right--;
        
        //走到这里 left指向偶数停下来，right指向奇数停下来
        if(left < right) //防止走到这里left超过了right 已经成功了，再判断一下
        {
            int tmp = *left;
            *left = *right;
            *right = tmp;
            left++;
            right--;
        }
    }
}
int test1()
{
    srand((unsigned int)time(NULL));
    int arr[10] = {0};
    int len = sizeof(arr)/sizeof(arr[0]);
    int i = 0;
    for(i = 0; i < len; i++)
    {
        arr[i] = rand()%20+1;
    }
    for(i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    //fun2(arr, len); //三指针
    fun3(arr, len); //双指针
    for(i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

}

/*
日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。
以下为4个嫌疑犯的供词:
A说：不是我。1  1
B说：是C。  1  0
C说：是D。  0  0
D说：C在胡说 1  1
已知3个人说了真话，1个人说的是假话。
现在请根据这些信息，写一个程序来确定到底谁是凶手。
*/

//判断某个嫌疑人的供词是否为真   
int is_truth(char suspect, int killer)
{
    switch(suspect)
    {
        case 'A': return killer != 0; //A说：不是我。
        case 'B': return killer == 2; //B说：是C。
        case 'C': return killer == 3; //C说：是D。
        case 'D': return killer != 3; //D说：C在胡说。
        default: return 0;
    }
}
void test2()
{
    char suspects[] = {'A', 'B', 'C', 'D'}; //嫌疑犯
    int killer = -1; //凶手编号 A0,B1,C2,D3
    int i = 0;
    //循环依次假设每个人是凶手
    for (i = 0; i < 4; i++) {
        int truch_count = 0; 
        int lie_count = 0;
        //检查供词
        int j = 0;
        for(j = 0; j < 4; j++)
        {
            if(is_truth(suspects[j], i)) //j是检验每一个人的供词，i是假设凶手编号
                truch_count++;
            else
                lie_count++;
        }
        if(truch_count == 3 && lie_count == 1)
        {
            killer = i;
            break;
        }
    }
    printf("凶手是: %c\n",suspects[killer]);
}

/*
5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：

A选手说：B第二，我第三；
B选手说：我第二，E第四；
C选手说：我第一，D第二；
D选手说：C最后，我第三；
E选手说：我第四，A第一；
比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。
*/


/*
考虑到一共五个人，直接模拟推理有些太难，计算机最擅长的遍历此
时就会派上用场，将每个人从第1到第5来一遍，则一共会产生5^5种
可能性，这个只需要一个5层循环即可搞定。但是这样会导致一些不
期望出现的结果出现，因为我并没有查重，所以会出现两个人抢名次
的情况，也就是两个人或者更多的人名次相同的情况，例如两个第二，
三个第三这样的，所以即使满足了条件，也要查看一下五个人的名次
是否重复，这个交给一个函数来执行，只要五个人名次并列，那就返回
0，否则返回1即可。有了这个思路，就能完成以下代码。

*/
int checkData(int *p)
{
	int tmp[7] = { 0 }; //标记表，实际是哈希表的思路。一开始每个元素都是0。

	int i;
	for (i = 0; i < 5; i++)
	{
		if (tmp[p[i]]) //如果这个位置的标记已经是1，则代表重复，直接返回0。
		{
			return 0;
		}
		tmp[p[i]] = 1; //如果不是，则给这个位置标记为1。
	}
	return 1; //全部标记完毕也没有出现重复的情况，代表OK。
}

void test3()
{
	int p[5]; //0 1 2 3 4分别代表a b c d e

	for (p[0] = 1; p[0] <= 5; p[0]++)
	{
		for (p[1] = 1; p[1] <= 5; p[1]++)
		{
			for (p[2] = 1; p[2] <= 5; p[2]++)
			{
				for (p[3] = 1; p[3] <= 5; p[3]++)
				{
					for (p[4] = 1; p[4] <= 5; p[4]++) //五层循环遍历
					{
                    //这里是五个人的描述，由于比较表达式只有0和1两个结果，如果要两个条件有且只有一个为真，则可以用比较表达式的值总和为1的方式直接判定。别忘了还要判定不能并列。
						if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三
							(p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四
							(p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二
							(p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三
							(p[4] == 4) + (p[0] == 1) == 1 && //我第四，A第一
							checkData(p) //不能并列
							)
						{
							for (int i = 0; i < 5; i++)
							{
								printf("%d ", p[i]);
							}
							putchar('\n');
						}
					}
				}
			}
		}
	}
}
/*
改进一：

检查是否重复的过程，我们是用一个数组来做的，实际每个标签只有0和1
两种可能，没必要一定要用数组做，可以考虑用一个位来做（哈希中的位
图），代码如下：

*/
int checkData_vs1(int *p)
{
	char tmp = 0;

	int i;
	for (i = 0; i < 5; i++)
	{
		tmp |= 1 << p[i]; 
        /*tmp每次或上一位1，p[i]如果是1~5都有，则1<<1到1<<5都或
        上的结果将会是00111110，如果有并列，则一定会至少却其中一个
        1，结果就不会是00111110，所以可以判断tmp最终的结果是不是这
        个数字来判断有没有重复。*/
	}
	return tmp == 0x3E;
}
/*
改进二：
循环代码又长又难看，可以考虑改成递归：

*/

void diveRank(int * p, int n)
{
	if(n >= 5) //此时的n是用来控制循环层数的。
	{
		if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三
			(p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四
			(p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二
			(p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三
			(p[4] == 4) + (p[0] == 1) == 1 && //我第四，A第一
			checkData(p)) //查重
		{
			for (int i = 0; i < 5; i++)
			{
				printf("%d ", p[i]);
			}
			putchar('\n');
		}
		return;
	}

	for(p[n] = 1; p[n] <= 5; p[n]++)
	{
		diveRank(p, n + 1); //通过递归模拟多层循环，每进一次递归相当于进了一层新的循环。
	}
}

int test4()
{
	int p[5];

	diveRank(p, 0);

	return 0;
}

/*
改进三：

以上的方法只是让代码简单了点，但还是需要5^5次比较，而如果
本来就是做1~5的排列组合的话只需要5!次比较，能极大的减少遍
历所需的次数（复杂度由O(n^n)降低为O(n!)），那是不是可以用
一个递归完成对1~5的全排列呢？当然是可以的，所以我们可以进
一步优化遍历的方式，将遍历用的递归程序改成这样：
*/

void swapArgs(int * a, int * b) //交换函数
{
	int tmp;
	
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void diveRank3(int * p, int n)
{
	if(n >= 5) //此时的n也是用来控制循环层数的。
	{
		if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三
			(p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四
			(p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二
			(p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三
			(p[4] == 4) + (p[0] == 1) == 1)   //我第四，A第一
            //由于此时是执行的全排列，所以查重也省了。
		{
			for (int i = 0; i < 5; i++)
			{
				printf("%d ", p[i]);
			}
			putchar('\n');
		}
		return;
	}

    int i;
	for(i = n; i < 5; i++) //这个递归方式就完成了对1~5的全排列，方法是从后向前不停的执行交换。可以参考改进二和原代码，将这个递归程序写回成循环后，可以更好的理解。
	{
		swapArgs(p + i, p + n);
		diveRank(p, n + 1);
		swapArgs(p + i, p + n);
	}
}

int test5()
{
	int p[5] = { 1, 2, 3, 4, 5 }; //当然由于是全排列，所以初值必须给好。

	diveRank(p, 0);

	return 0;
}

/*
实现一个函数，可以左旋字符串中的k个字符。

例如：

ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB

*/

//第一个版本
void leftRotate_vs1(char *str, int k, int len)
{
    if(str == NULL || len<=0 || k <=0)
        return;
    char* left = str;
    char* right = str+len-1;
    k %= len;
    while(k)
    {
        left = str;
        right = str+len-1;
        char tmp = *left;
        while(left < right)
        {
            *left =  *(left+1); 
            left++;
        }
        *right = tmp;
        k--;
    }
}

//上一个版本时间复杂度是O(n)*k 效率太低，
//优化后的版本

/*
3步走：reverse(str, 0, k - 1);     // 翻转前 k 个字符
      reverse(str, k, len - 1);   // 翻转剩余部分
      reverse(str, 0, len - 1);   // 翻转整个字符串
*/
void reverse(char* str, int start, int end)
{
    while(start < end)
    {
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        start++;
        end--;
    }    
}
void leftRotate(char* str, int k, int len)
{
    if(str == NULL || k <= 0 || len <= 0)
        return;
    char* left = str;
    char* right = str+len-1;
    k %= len;
    reverse(str, 0, k-1);
    reverse(str, k, len-1);
    reverse(str, 0, len-1);
}
void test6()
{
    char str[] = "abcdef";
    int len = strlen(str);
    int k = 3;
    leftRotate(str, k, len);
    printf("%s\n", str);
}

/*
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下
是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
*/


/* 思路
1.	从右上角元素开始。
2.	比较当前元素与目标值：
    如果当前元素等于目标值，直接返回存在；
    如果当前元素小于目标值，向下移动（增大）；
    如果当前元素大于目标值，向左移动（减小）。
3.  重复上述过程，直到找到目标值或超出矩阵范围。
*/
int find_number(int (*arr)[4], int rows, int cols, int k)
{
    //row:0 col:col-1
    int row = 0;
    int col = cols-1;
    //int n = arr[row][col];
    while(col >= 0 && row < rows)
    {
        if(k == arr[row][col]) return 1;
        if(k > arr[row][col])  row++;
        else  col--;
    }
    return 0;
}
void test7()
{
    int arr[4][4]={
    { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 10, 11, 12 },
    {13, 14, 15, 16 }
    };
    int row = 4;
    int col = 4;
    for(int i = 0; i <= 18; i++)
    {
        if(find_number(arr, row, col, i))
            printf("%d:YES\n",i);
        else
            printf("%d NO\n", i);
    }

}
int main()
{
    //printf("%d\n",fun1(20));

    //test1();

    //printf("%d %d", sizeof(unsigned int), sizeof(unsigned char));
    //test2();

    //test3();
    //test4();
    //test6();
    test7();
    return 0;
}